package bank;

public class _42Ttrap {
    public static int trap(int[] height) {
        //  每个柱子上方可以承载的雨水量等于 两边柱子最高柱子中的最小值 - 当前柱子的高度
        //  但该算法效率较低
        int res = 0;
        for (int i = 0;i < height.length;i++){
            int minHeight = heightHelp(height,i);
            if (minHeight <= height[i]){
                res += 0;
            }else {
                res += minHeight - height[i];
            }
        }
        return res;
    }

    private static int heightHelp(int[] height, int i) {
        if (i == 0 || i == height.length){
            return 0;
        }
        int leftMax = 0, rightMax = 0;
        for (int j = 0;j < i;j++){
            leftMax = Math.max(height[j],leftMax);
        }
        for (int j = i+1;j < height.length;j++){
            rightMax = Math.max(height[j],rightMax);
        }
        return Math.min(leftMax,rightMax);
    }
}
